\section{Explicación del algoritmo}
Para la implementación de la busquedalocal 
se decidió definir una vecindad en la cual la distancia
entre la solución inicial y derivada difiere en a lo sumo  2.
Dada una solución $S$ con al menos 2 particiones, no vacías $p1$ y $p2$
con $v_1$$\dots$$v_n \in p_1$ y  $w_1$ $\dots$ $w_n \in p2$.
Entonces la vecindad contendrá a todas las soluciones que sean del tipo
\begin{itemize}
\item existe un $v_k$ y un $v_{k'}$ en $p_1$ adyacentes y $w_{k''}$ en $p_2$
con $w_{k''}$ adyacente a $v_k$ tal que al intercambiar $v_{k'}$ 
en $p_2$  y $w_{k''}$ en $p_1$  se produce una mejora en el peso total de las particiones. 
\item la segunda posibilidad solo difiere en la anterior en que  no se intercambian
2 vértices adyacentes al vértice seleccionado en el análisis sino que se cambia
de partición un vértice adyacente al analizado que y que esta dentro de la misma particion.
\end{itemize}
El motivo de definir la vecindad de esta manera es por que 
al haber 2 vértices adyacentes en una partición el eje que los conecta
suma peso al global de peso. Al tratar de eliminar este eje se mueve uno de los vértices
a otra partición, y se evalúa si al insertar el eje en la nueva partición 
la suma que genera es menor que el valor restado al quitarlo de la partición original.
Al ubicarlo en la nueva partición también se corre el riesgo de encontrar
adyacentes al vértice relocalizado, por esto se evalúa y en caso de producir mejor 
suma, se lo considera como un vecino valido. \\
Para encontrar a todos los vecinos se recorrerá cada vértice de cada partición. Para cada uno de estos se buscara encontrar soluciones vecinas en las dos formas planteadas. O con 2 adyacentes 
intercambiándolos o solo un adyacente y quitándolo de la partición. \\
Cada una de estas soluciones vecinas junto con el valor de mejora
que produce sobre la solución inicial son almacenadas en una lista 
y ordenadas por el valor de mejora que producen. De esta lista se 
toma la solución vecina que mas mejora produce a la solución inicial
y se comienza nuevamente una busquedalocal desde esta solución vecina.\\
Una ves llegado a una solución donde la vecindad es vacía, osea que no 
produce mejora se termina la busquedalocal.\\
Aquí se decidimos considerar en la vecindad aquellas soluciones que dada una 
solución no solo se encuentra a la distancia descrita anteriormente, 1 o 2 vértices de distancia, sino
que también estas soluciones tienen que ser mejores que la solución que se analiza, en caso contrario
son descartadas. 

\section{Pseudocódigo}
\begin{algorithm}[H]
\KwData{BLOCAL(R)}
- sea R una solución con I particiones\\
- vecindad es una lista de vecinos a la solución actual\\

\FORALL{ partición P \in  R}{\\
	\tab\FORALL{ v \in  P}{\\
		\tab\tab\FORALL{ adyIn, adyacentes\ a\ v\ \in P    }{\\
			\tab\tab\tab\FORALL{ adyOut, adyacentes\ a\ v\ \notin P    }{\\
			    \tab\tab\tab\tab diferencia $\leftarrow$ calcularDiferencia(R,P,adyIn,adyOut,NULL)\\
				\tab\tab\tab\tab\If{diferencia $<$ 0}{\\
					\tab\tab\tab\tab vecindad.append((v,p,adyIn,adyOut,NULL,diferencia))\\
				}
		    }
			\tab\tab\tab\FORALL{ partición P2 \in R $\ \&\&\ $ P2 $!=$ P    }{\\
			    \tab\tab\tab\tab diferencia $\leftarrow$ calcularDiferencia(R,P,adyIn,NULL,P@)\\
				\tab\tab\tab\tab\If{diferencia $<$ 0}{\\
					\tab\tab\tab\tab vecindad.append((v,p,adyIn,NULL,P2,diferencia))\\
				}
		    }

	    }

   }
}	  

\If{vecindad.size()}{\\
	\tab vecindad.sort(ordenarPorDiff)\\
	\tab aplicarCambio(R,vecindad.front())\\
	\tab BLOCAL(R)\\
\\}
\caption{BLOCAL()}
\label{alg:ej5}
\end{algorithm}
\\
Se plantearon 2 casos para definir la vecindad, el primero es 
intercambiar un par de vértices entre 2 particiones, el segundo
es quitar 1 vértice de una partición para enviarlo a otra.\\
En el  pseudocódigo se puede ver como se contemplan los 2 casos
que definen la vecindad en los loops de las lineas 6 y 10. 
En el primero se intercambian pares de vértices entre 2 particiones
y se evalúa su impacto. En caso de producir una diferencia negativa
en el peso total de las particiones se la guarda. \\
En el segundo loop se evalúa enviar un vértice a otra partición
a ver si eso reduce el peso total de las particiones. 
Todos los resultados que producen mejoras al peso actual son 
guardados en un arreglo $vecindad$. Este arreglo 
luego es ordenado para dejar adelante a el vecino que produce
el mayor decremento(linea 15). Luego se toma ese vecino y se aplican
los cambios para moverse hacia esa solución vecina. Desde esta
se comenzara nuevamente a buscar a los vecinos que produzcan mejoras 
en la solución actual. Cuando se llegue a una instancia en la que no se puedan producir 
mejoras se terminara la busquedalocal.\\
Las funciones $aplicarCambios$ y $calcularDiferencia$ no fueron incluidas en el 
pseudocódigo dado que se quería mostrar como se definía la vecindad y la operatoria
del algoritmo evitando abundar en funciones auxiliares. En el primer caso $aplicarCambios$
solo intercambia vértices de partición, $calcularDiferencia$ recalculará 
la suma de peso de las particiones definidas si se cambian los vértices pasados como parámetros. 


% El pseudocodigo presentado esta simplificado ya que no  posee la poda implementada en la cual si al momento de realizar el cálculo de peso de las lineas 11 y 19 se sobrepasa el valor de $MinV$ no
% se hara la llamada recursiva a $EXACTO$. \\

% El loop de la linea 7 tratará de ubicar  cada vértice disponible
% en una partición nueva o una existente. Luego calculara como 
% eso afecta el peso de la solución llamando a $ACTUALIZAR\_PESO$ y posteriormente
% pasara el subproblema recursivamente.  Al retorno evaluara si haber 
% ubicado  $v$ en esa partición fue la decisión correcta.

% La función $ACTUALIZAR\_PESO$ es encargada de dado un vértice y una partición
% calcular cuanto incrementa el peso total de las particiones al agregarlo 
% a la partición. 


\section{Orden de complejidad}
En la búsqueda de las soluciones de la vecindad se recorren las siguientes 
estructuras:\\
\begin{itemize}
\item se recorren todas las particiones
\item luego para cada partición se recorren cada uno de los vértices.
\item para cada vértice se recorrerán sus adyacentes dentro de la particion
\begin{itemize}
\item Para cada vertice se recorreran sus adyacentes fuera de la particion
\item Se recorrera como segunda instancia todas las particiones tratando de ubicar el adyacente dentro de la particione en una segunda particion
\end{itemize}
\end{itemize}

La suma de los nodos de cada partición es el total de nodos ya que cada nodo se encuentra en una partición, esto cuesta $O(n)$. \\
Para cada vértice se recorren sus adyacencias, sabemos que estas pueden a lo sumo $n-1$, resultando $O(n^2-n)\in O(n^2)$. Luego por cada adyacencia dentro de la partición busco una fuera de la misma, nuevamente $n-1$ adyacencias a lo sumo para analizar. Luego se busca un reemplazo de la adyacencia, para encontrarlo se recorren las particiones de cada nodo, resultando $n+n$
$$
n^3 * (n+n) = n^4 + n^4 \subset \mathcal{O}(n^4)
$$
Como la complejidad del algoritmo goloso, el cuál genera la solución inicial, es igual es $k*n^3$ acotando $k$ con $n$ queda igual a esta complejidad. Por ende la complejidad total es:
$$
n^4 + n^4 \subset \mathcal{O}(n^4)
$$ \\
El valor de $k$ se puede acotar por $n-1$ dado que problemas 
en los que $k=>n$ pueden resolverse en costo lineal y con peso total 0 
dado que se ubica un vertice en cada particion, dejando el resto vacias
en caso de $k>n$

\section{Instancias perjudiciales para la heuristica}
La heurística de búsqueda local partirá de una solución sub-optima 
y tratara dada la vecindad que se definió de ir mejorándola 
en base a los vecinos que presenten mas decremento en el peso total
de las particiones. En este caso la definicion de la vecindad dejo 
afuera aquellas soluciones que resulten de el intercambio de mas de 2 vertices
por ejemplo aquellas que dado un problema en el que se plantee 
generar 2 particiones para un grafo, resulte de intercambiar 2 vertices de
la particion $A$ con dos vertices de la particion $B$. Supongamos que existe
un intercambio de este tipo que produce una reduccion en el peso de las particiones, 
pero que al tratar de intercambiar de a 1 vertice entre particiones no produzca mejora.
Casos de ese tipo donde los intercambios son un subconjunto de un particion 
por otro subconjunto de otra particion y estos con mas de 1 vertice no seran 
contemplados ni alcanzados en la busqueda local. Si en el caso de que esa 
solucion pueda ser alcanzada desde la inicial mediante intercambio de uno y hasta 2 vertices
pero no en el caso donde sea necesario realizar intercambios mayores. \\
Casos de este tipo se presentaran en grafos densos donde la cantidad de aristas que conectan
a un vertice es alta y por lo tanto los vertices en problemas de pocas particiones
tendran varios vertices conectados en cada particion donde se los quiera ubicar. 
haciendo imposible que las particiones sean de vertices independientes entre si. 

\section{Experimentación}
Comparamos los tiempos tomados en la corrida del algoritmo usando grafos densos y dispersos, generados aleatoriamente y limitando el valor máximo de $k$, para $k=10,50,100$. En las figuras \ref{fig:blocal:complejidadK10},\ref{fig:blocal:complejidadK50} y \ref{fig:blocal:complejidadK100} se aprecia como los grafos dispersos se procesan más rápido, por tener menos aristas, que los densos. Además en cada uno de estos gráficos vemos como la complejidad teórica depende no solo de la cantidad de nodos, eje x, sino también del valor de $k$.
\ponerGrafico{graficos/blocalK10.pdf}{Complejidad teórica y tiempo de ejecución con K$\le$10. Heurística de búsqueda local.}{1}{blocal:complejidadK10}
\ponerGrafico{graficos/blocalK50.pdf}{Complejidad teórica y tiempo de ejecución con K$\le$50. Heurística de búsqueda local.}{1}{blocal:complejidadK50}
\ponerGrafico{graficos/blocalK100.pdf}{Complejidad teórica y tiempo de ejecución con K$\le$100. Heurística de búsqueda local.}{1}{blocal:complejidadK100}